Search for: All records

Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ $f(·)$due to an ordering$$\sigma $$ $\sigma$of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ ${min}_{\sigma }{\sum }_{i\in \left[n\right]}f\left(E_{i,\sigma }\right)$, where$$E_{i,\sigma }$$ $E_{i,\sigma }$is the set of items mapped by$$\sigma $$ $\sigma$to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ $(2-\frac{1+{\ell }_f}{1+\left|E\right|})$-approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ ${\ell }_f=\frac{f\left(E\right)}{{max}_{x\in E}f\left(\left\{x\right\}\right)}$satisfies$$1 \le \ell _f \le |E|$$ $1\le {\ell }_f\le \left|E\right|$. Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ $(2-\frac{1+r\left(E\right)}{1+\left|E\right|})$-approximation for the matroid MLOP, where$$f = r$$ $f=r$is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ $\frac{4}{3}$-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest.